import java.util.Stack;

/**
 * @author jekyllxv
 */
public class ReverseLinkedList {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(){}
        ListNode(int val) {
            this.val=val;
        }
    }

   public ListNode reverse(ListNode head){
        ListNode data = new ListNode();

        ListNode current = head;

        ListNode pre = null;

        ListNode temp = null;

        while(current != null){
            //temp是下一个;
            temp = current.next;
            //指针反转
            current.next = pre;
            //第二个指针前进
            pre = current;
            //第一个指针前进
            current = temp;
        }

        //因为current最终会是null, 所以pre是会是最后一个链表头
        return pre;
   }

    public ListNode reverseList2(ListNode head) {
        // 如果链表为空，则返回空
        if (head == null) {
            return null;
        }
        // 如果链表中只有只有一个元素，则直接返回
        if (head.next == null) {
            return head;
        }
        // 创建栈 每一个结点都入栈
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 创建一个虚拟头结点
        ListNode pHead = new ListNode(0);
        cur = pHead;
        while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            cur.next = node;
            cur = cur.next;
        }
        // 最后一个元素的next要赋值为空
        cur.next = null;
        return pHead.next;
    }

    public static ListNode reverseList1(ListNode head) {
        // 创建虚头结点
        ListNode dumpyHead = new ListNode(-1);
        dumpyHead.next = null;
        // 遍历所有节点
        ListNode cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            // 头插法
            cur.next = dumpyHead.next;
            dumpyHead.next = cur;
            cur = temp;
        }
        return dumpyHead.next;
    }

}
